<html>
<head>
<meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
<title>use A* to find path...</title>
</head>
<body style="margin:0px">
<script>
/*
written by hjjboy
email:tianmashuangyi@163.com
qq:156809986
*/
var closelist=new Array(),openlist=new Array();
var gw=10,gh=10,gwh=14;
var p_start=new Array(2),p_end=new Array(2);
var s_path,n_path="";
var num,bg,flag=0;
var w=60,h=30;
var wallCo = ['0000','0001','0002','0003','0004','0005','0006','00034','00035','00036','00037','00038','00039','00040','0100','0104','0106','01034','01036','01040','0200','0206','02034','02040','0300','0304','0306','03034','03036','03040','0400','0401','0402','0403','0404','0406','0407','0408','0409','04010','04011','04012','04013','04014','04015','04016','04017','04018','04019','04021','04022','04023','04024','04025','04026','04027','04028','04029','04030','04031','04032','04033','04034','04036','04037','04038','04039','04040','0500','0504','0506','05010','05014','05018','05019','05021','05022','05026','05030','05034','05036','05040','0600','0604','0606','06010','06014','06018','06019','06021','06022','06026','06030','06034','06036','06040','0700','0706','07010','07014','07018','07019','07021','07022','07026','07030','07034','07040','0800','0804','0806','0807','0809','08010','08011','08013','08014','08015','08017','08018','08019','08021','08022','08023','08025','08026','08027','08029','08030','08031','08033','08034','08036','08040','0900','0904','09036','09040',
		'01000','01001','01002','01003','01004','01006','01007','01008','01009','010010','010011','010012','010013','010014','010015','010016','010017','010018','010019','010021','010022','010023','010024','010025','010026','010027','010028','010029','010030','010031','010032','010033','010034','010036','010037','010038','010039','010040','01104','01106','011034','011036','01204','01206','012034','012036'];
function GetRound(pos){
  var a=new Array();
  a[0]=(pos[0]+1)+","+(pos[1]-1);
  a[1]=(pos[0]+1)+","+pos[1];
  a[2]=(pos[0]+1)+","+(pos[1]+1);
  a[3]=pos[0]+","+(pos[1]+1);
  a[4]=(pos[0]-1)+","+(pos[1]+1);
  a[5]=(pos[0]-1)+","+pos[1];
  a[6]=(pos[0]-1)+","+(pos[1]-1);
  a[7]=pos[0]+","+(pos[1]-1);
  return a;
}
function GetF(arr){
  var t,G,H,F;
  for(var i=0;i<arr.length;i++){
    t=arr[i].split(",");
    t[0]=parseInt(t[0]);t[1]=parseInt(t[1]);
    if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]]))
        continue;
    if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0)
        G=s_path[1]+gwh;
    else
        G=s_path[1]+gw;
    if(InOpen([t[0],t[1]])){
        if(G<openlist[num][1]){
          openlist[num][0]=(G+openlist[num][2]);
          openlist[num][1]=G;
          openlist[num][4]=s_path[3];
        }
        else{G=openlist[num][1];}
    }
    else{
        H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw;
        F=G+H;
        arr[i]=new Array();
        arr[i][0]=F;arr[i][1]=G;arr[i][2]=H;arr[i][3]=[t[0],t[1]];arr[i][4]=s_path[3];
        openlist[openlist.length]=arr[i];
    }
    if(maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#cccccc"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#0000ff"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#ff0000"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#00ff00")
    {
        maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF";
        //maptt.rows[t[1]].cells[t[0]].innerHTML="<font color=white>"+G+"</font>";
    }
  }
}
function IsStart(arr){
  if(arr[0]==p_start[0]&&arr[1]==p_start[1])
    return true;
  return false;
}
function IsInTurn(arr){
  if(arr[0]>s_path[3][0]){
    if(arr[1]>s_path[3][1]){
        if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))
          return false;
    }
    else if(arr[1]<s_path[3][1]){
        if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))
          return false;
    }
  }
  else if(arr[0]<s_path[3][0]){
    if(arr[1]>s_path[3][1]){
        if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))
          return false;
    }
    else if(arr[1]<s_path[3][1]){
        if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))
          return false;
    }
  }
  return true;
}
function IsOutScreen(arr){
  if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1))
    return true;
  return false;
}
function InOpen(arr){
  var bool=false;
  for(var i=0;i<openlist.length;i++){
    if(arr[0]==openlist[i][3][0]&&arr[1]==openlist[i][3][1]){
        bool=true;num=i;break;}
  }
  return bool;
}
function InClose(arr){
  var bool=false;
  for(var i=0;i<closelist.length;i++){
    if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){
        bool=true;break;}
  }
  return bool;
}
function IsPass(pos){
  if((";"+n_path+";").indexOf(";"+pos+";")!=-1)
    return true;
  return false;
}
function Sort(arr){
  var temp;
  for(var i=0;i<arr.length;i++){
    if(arr.length==1)break;
    if(arr[i][0]<=arr[i+1][0]){
        temp=arr[i];
        arr[i]=arr[i+1];
        arr[i+1]=temp;
    }
    if((i+1)==(arr.length-1))
        break;
  }
}
function main(){
    GetF(GetRound(s_path[3]));
    Sort(openlist);
    s_path=openlist[openlist.length-1];
    closelist[closelist.length]=s_path;
    openlist[openlist.length-1]=null;
    if(openlist.length==0){alert("找不到路径");return;}
    openlist.length=openlist.length-1;
    if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){
        getPath();
    }
    else{maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="#00ff00";setTimeout("main()",100);}
}

/**
*寻找最短路径
*/
function getPath(){
  var str="";
  var t=closelist[closelist.length-1][4];
  while(1){
    str+=t.join(",")+";";
    maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00";
    for(var i=0;i<closelist.length;i++){
        if(closelist[i][3][0]==t[0]&&closelist[i][3][1]==t[1])
          t=closelist[i][4];
    }
    if(t[0]==p_start[0]&&t[1]==p_start[1])
        break;
  }
  alert(str);
}

function setPos(){
  var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw;
  s_path=[h,0,h,p_start,p_start];
}
/**
*根据id值的不同给格子设置不同的颜色
*/
function set(id,arr){
  switch(id){
    case 1:
        p_start=arr;
        maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break;
    case 2:
        p_end=arr;
        maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break;
    case 3:
        n_path+=arr.join(",")+";";
        maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break;
    default:
        break;
  }
}
/**
*设置flag
*/
function setflag(id){flag=id;}
function config(){
  alert("dhsgdhasdju");
}
</script>
<table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">

<!--动态创建表格-->
<script>
for(var i=0;i<h;i++){
  document.write("<tr>");
  for(var j=0;j<w;j++){
		var rc = "0"+i+"0"+j;
    var arra = [j,i];

    document.write('<td onclick="set(flag,['+j+','+i+']);" bgcolor="#ffffff" width="20" height="20"></td>');
    for(var k=0;k < wallCo.length;k++){
      if(rc == wallCo[k]){
					n_path+=arra.join(",")+";";
          maptt.rows[arra[1]].cells[arra[0]].style.backgroundColor="#cccccc";break;
					break;
			}
    }
  }
  document.write("</tr>");
}
</script>
</table>
<a href="javascript:setflag(1);">设置起点</a><br>
<a href='javascript:setflag(2);'>设置终点</a><br>
<a href='javascript:setflag(3);'>设置障碍点</a><br>
<input type="button" onclick="setPos();main();this.disabled=true;" value="find">
</body>
</html>